package cn.element.leetcode.sorted;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @description:
 * @author: gonghongwei
 * @create: 2021-06-25 14:58
 * 数组中的第K个最大元素
 * <p>
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 * <p>
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class L215KthLargestElement {
	//	排序
	public int findKthLargest(int[] nums, int k) {
		Arrays.sort(nums);
		return nums[nums.length - k];
	}

	//	堆
	public int findKthLargest1(int[] nums, int k) {
		PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
		for (int val : nums) {
			pq.add(val);
			if (pq.size() > k)  // 维护堆的大小为 K
				pq.poll();
		}
		return pq.peek();
	}

	//快速选择
	public int findKthLargest2(int[] nums, int k) {
		k = nums.length - k;
		int l = 0, h = nums.length - 1;
		while (l < h) {
			int j = partition(nums, l, h);
			if (j == k) {
				break;
			} else if (j < k) {
				l = j + 1;
			} else {
				h = j - 1;
			}
		}
		return nums[k];
	}

	private int partition(int[] a, int l, int h) {
		int i = l, j = h + 1;
		while (true) {
			while (a[++i] < a[l] && i < h) ;
			while (a[--j] > a[l] && j > l) ;
			if (i >= j) {
				break;
			}
			swap(a, i, j);
		}
		swap(a, l, j);
		return j;
	}

	private void swap(int[] a, int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}
